package com.zjsru.oneDay202206;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @Author: likew
 * @Date: 2022/6/18
 *
 * 返回重复的数，使用了四种方法：
 * 1.暴力算法
 * 2.双指针
 * 3.map
 * 4.原地哈希算法，即看成一个链表，环入口即是重复的数字
 *
 */
public class test0618 {

//    public int test(int[] arr){
//        int n = arr.length;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                if(arr[i] == arr[j]){
//                    return arr[j];
//                }
//            }
//        }
//        return -1;
//    }


//    public int test(int[] arr){
//        int n = arr.length;
//        for (int i = 0, j = i + 1; i < n;) {
//            if(arr[i] == arr[j]){
//                return arr[j];
//            }else {
//                j++;
//            }
//            if(j == n){
//                j = i;
//                i++;
//            }
//        }
//        return -1;
//    }


//    public int test(int[] arr){
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int i:arr) {
//            map.put(i, map.getOrDefault(i,0)+1);
//        }
//        Set<Integer> integers = map.keySet();
//        for (int i:integers) {
//            if(map.get(i) == 2){
//                return i;
//            }
//        }
//        return -1;
//    }
    
    public int test(int[] nums){
        int slow = 0, fast = 0;
        while(slow != fast || fast == 0) {
            // slow = slow.next
            slow = nums[slow];
            // fast = fast.next.next
            fast = nums[nums[fast]];
        }
        slow = 0;
        // 另一个重复的数字 在fast开始的后半段
        while(slow != fast) {
            // slow = slow.next
            slow = nums[slow];
            // fast = fast.next
            fast = nums[fast];
        }
        return slow;
    }

    public static void main(String[] args) {
        test0618 test = new test0618();
        int[] arr = new int[]{1,2,3,4,5,6,7,8,3,9,10};
        System.out.println(test.test(arr));
    }
}
